import numpy
from OpenGL.GL import * 
import math

def normal(a,b,c):
	" Return normal vector for triangle a,b,c "
	def normalize(x):
		l = -math.sqrt(x[0]**2+x[1]**2+x[2]**2)
		if l==0:
			return x
		return (x[0]/l,x[1]/l,x[2]/l)
	
	ux = b[0] - a[0]
	uy = b[1] - a[1]
	uz = b[2] - a[2]
	
	vx = c[0] - a[0]	
	vy = c[1] - a[1]	
	vz = c[2] - a[2]	

	rx = - uy*vz + uz*vy
	ry = ux*vz - uz*vx
	rz = -ux*vy + uy*vx

	return normalize((rx,ry,rz))

def drawtriangle(a,b,c):
	glNormal(*normal(a,b,c))
	glVertex(*a)
	glVertex(*b)
	glVertex(*c)

def ray_triangle_intersect(O,D,A,B,C):
	" Say True if ray OD intersects triangle ABC "
	b = [A[i] - O[i] for i in range(3)] #b = [A[0] - O[0],A[1] - O[1], A[2] - O[2]]
	M = [[D[i],A[i]-C[i],A[i]-B[i]] for i in range(3)]
	try:
		t,v,u = numpy.linalg.solve(M,b)
	except numpy.linalg.LinAlgError:
		return False
	if t<0 or v<0 or u<0:
		return False
	if v+u>1:
		return False
	return True
	
def line_triangle_intersect(O,E,A,B,C):
	" Return X which is is intersection of triangle ABC and line segment OE, or None"
	b = [A[i] - O[i] for i in range(3)]
	M = [[E[i]-O[i],A[i]-C[i],A[i]-B[i]] for i in range(3)]
	try:
		t,v,u = numpy.linalg.solve(M,b)
	except numpy.linalg.LinAlgError:
		return None
	if t<0 or t>1 or v<0 or u<0:
		return None
	if v+u>1:
		return None
	return [O[i] + t*(E[i] - O[i]) for i in range(3)]

def inside_tetrahedron(X,A,B,C,D):
	b = [X[i] - A[i] for i in range(3)]
	M = [ [B[i]-A[i],C[i]-A[i],D[i]-A[i]] for i in range(3)]

	try:
		uvw = numpy.linalg.solve(M,b)
	except numpy.linalg.LinAlgError:
		return False
	for par in uvw:
		if par<0:
			return False
	if sum(uvw)>1:
		return False
	return True


def insidemesh(p,mesh):
	count = 0
	for facen in mesh.faces:
		face = facen[0]
		for i in range(1,len(face)-1):
			if ray_triangle_intersect(p,(1,1,1),mesh.vertices[face[0]-1],mesh.vertices[face[i]-1],mesh.vertices[face[i+1]-1]):
				count+=1
	return count % 2 ==1	

def generate_mesh_triangle_centres(mesh):
	def center(a,b,c):
		return tuple([(a[i]+b[i]+c[i])/3.0 for i in range(3)])
	for facen in mesh.faces:
		face = facen[0]
		for i in range(1,len(face)-1):
			yield center(mesh.vertices[face[0]-1],mesh.vertices[face[i]-1],mesh.vertices[face[i+1]-1])

def get_model_internals(fn,n):
	import objloader
	from random import random
	cow = objloader.OBJ(fn+".obj")
	insiders = []
	for i in range(n):
		p = (random() -0.5 ,random() - 0.5,random()-0.5)
		print i,p
		if insidemesh(p,cow): 
			print True
			insiders.append(p)
	print "Found %d points." % len(insiders)
	f = open(fn+".int","w")
	f.write(repr(insiders))
	f.close()

def gen_tetra(fn,n):
	from random import random
	insiders = []
	for i in range(n):
		p = (random()*2 -1 ,random()*2 - 1,random()*2 -1 )
		print i,p
		if inside_tetrahedron(p,(1,1,1),(-1,-1,1),(-1,1,-1),(1,-1,-1)):
			print True
			insiders.append(p)
	f = open(fn,"w")
	f.write(repr(insiders))
	f.close()

def mean(*argv):
	return map(lambda x: x/len(argv), map(sum,zip(*argv)))

global_counter = 0
tetrahedrons_count = 0
class Tetrahedron():
	def __init__(self,a = (2,2,2),b=(-2,-2,2), c = (-2,2,-2), d = (2,-2,-2)):
		self.A = a
		self.B = b
		self.C = c
		self.D = d
		self.parent = None
		global tetrahedrons_count 
		tetrahedrons_count += 1
	def check_position(self,mesh):
		try:
			for son in self.parts:
				son.check_position(mesh)
		except AttributeError:
			self.external = not insidemesh(mean(self.A,self.B,self.C,self.D),mesh)
			global global_counter
			global_counter+=1
			print global_counter, tetrahedrons_count

	def draw(self, onlyinternals = False):	
		try:
			for son in self.parts:
				son.draw(onlyinternals)
		except AttributeError:
			if onlyinternals and self.external:
				return
			drawtriangle(self.A,self.B,self.C)
			drawtriangle(self.A,self.B,self.D)
			drawtriangle(self.A,self.D,self.C)
			drawtriangle(self.D,self.B,self.C)

	def _write_to_file(self, f, onlyinternals = False):	
		try:
			for son in self.parts:
				son._write_to_file(f,onlyinternals)
		except AttributeError:
			if onlyinternals and self.external:
				return
			f.write(repr(self.A)+"\n")
			f.write(repr(self.B)+"\n")
			f.write(repr(self.C)+"\n")
			f.write(repr(self.D)+'\n')

	def save_to_file(self, fn, onlyinternals = False):
		with open(fn,"w") as f:
			self._write_to_file(f,onlyinternals)

	def genlist(self):
		self.gl_list = glGenLists(1)
		glNewList(self.gl_list,GL_COMPILE)
		glBegin(GL_TRIANGLES)
		self.draw(False) 
		glEnd()
		glEndList()
	

	def inside(self,x):
		return inside_tetrahedron(x,self.A,self.B,self.C,self.D)

	def split(self,x):
		" Split to four tetrahedrons by point x "
		try:
			for son in self.parts:
				if son.inside(x):
					son.split(x)
		except AttributeError:
			self.parts = [
				Tetrahedron(x,self.A,self.B,self.C),
				Tetrahedron(x,self.D,self.B,self.C),
				Tetrahedron(x,self.A,self.D,self.C),
				Tetrahedron(x,self.A,self.B,self.D)]
			if self.parent:
				par = self.parent
			else:
				par = self
			for i in range(len(self.parts)):
				self.parts[i].parent = par
	def triangle_split(self,A,B,C):
		" Split to two by triangle two of which vertices lies on our edge "
		try:
			for son in self.parts:
				son.triangle_split(A,B,C)
		except AttributeError:
			l4 = [self.A,self.B,self.C,self.D]
			l3 = [A,B,C]

			# check if we have two points in triangle which lies on edge
			# move them to beginning of the list
			if l3[0] not in l4:
				l3[0],l3[2] = l3[2],l3[0]
				if l3[0] not in l4: return
				if l3[1] not in l4: return
			else:
				if l3[1] not in l4:
					if l3[2] not in l4: return
					l3[1],l3[2] = l3[2],l3[1]
			# move to the beginning of the list common edge of tetrahedron
			try:
				i = l4.index(l3[0])
			except ValueError: 
				return

			l4[i],l4[0] = l4[0],l4[i]

			try:
				i = l4.index(l3[1])
			except ValueError:
				return

			l4[i],l4[1] = l4[1],l4[i]
			# and then use line_triangle_intersect for triangle and two last vertexes of tetrahedron
			x = line_triangle_intersect(l4[2],l4[3],A,B,C)
			if not x:
				return 
			self.parts = [
				Tetrahedron(x,l4[0],l4[1],l4[2]),
				Tetrahedron(x,l4[0],l4[1],l4[3])]
	def mesh_cut(self,mesh):
		l = len(mesh.faces)
		counter = 0
		for facen in mesh.faces:
			face = facen[0]
			for i in range(1,len(face)-1):
				self.triangle_split(mesh.vertices[face[0]-1],mesh.vertices[face[i]-1],mesh.vertices[face[i+1]-1])
			print counter,l
			counter+=1
		self.check_position(mesh)


def createcubelist():
	res = glGenLists(1)
	glNewList(res,GL_COMPILE)

	glBegin(GL_QUADS)

	glNormal(0,1,0) # ccw around normal
	glVertex(-1,+1,-1)
	glVertex(-1,+1,+1)
	glVertex(+1,+1,+1)
	glVertex(+1,+1,-1)

	glNormal(0,-1,0)
	glVertex(+1,-1,+1)
	glVertex(-1,-1,+1)
	glVertex(-1,-1,-1)
	glVertex(+1,-1,-1)

	glNormal(1,0,0)
	glVertex(+1,-1,-1)
	glVertex(+1,+1,-1)
	glVertex(+1,+1,+1)
	glVertex(+1,-1,+1)

	glNormal(-1,0,0)
	glVertex(-1,-1,+1)
	glVertex(-1,+1,+1)
	glVertex(-1,+1,-1)
	glVertex(-1,-1,-1)

	glNormal(0,0,1)
	glVertex(-1,-1,+1)
	glVertex(+1,-1,+1)
	glVertex(+1,+1,+1)
	glVertex(-1,+1,+1)

	glNormal(0,0,-1)
	glVertex(-1,+1,-1)
	glVertex(+1,+1,-1)
	glVertex(+1,-1,-1)
	glVertex(-1,-1,-1)

	glEnd()
	glEndList()
	return res

if __name__ == "__main__":
	#get_model_internals("models/cow2",1000)
	#gen_tetra("models/tetrahedtron.txt",2500)
	pass

